home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 1 Issue 2 / PDCD-1 - Issue 02.iso / _editors / editors / _stronged / !EXTHELP / HEAP < prev    next >
Text File  |  1993-04-12  |  12KB  |  402 lines
  1. Heap memory manager
  2. ===================
  3.  
  4. WimpExtension's heap manager is one of the module's most powerful, useful,
  5. and - unavoidably - complicated features. This document is provided to
  6. explain more about what a relocatable heap is, and how to use it.
  7.  
  8. Programming examples in this document are given in BASIC, because practically
  9. everyone knows how to use it.
  10.  
  11. This document assumes that you know how to program in the RISC OS Wimp, and
  12. that you understand terms such as "WimpSlot" (read the chapter "The Window
  13. Manager" in the PRMs if you don't).
  14.  
  15. Read the "SWIs" and "Manual" files for a brief description of the parameters
  16. for the SWI WimpExt_Heap.
  17.  
  18.  
  19.  
  20. Why do I need a heap?
  21. ---------------------
  22.  
  23. Any program which uses more than one block of memory which changes size needs
  24. a heap manager. For example, Edit and Paint need a heap manager, because they
  25. can have several files loaded at once, all of which can be changing size at
  26. any time. The files are loaded into memory "blocks", which are provided by
  27. the heap manager.
  28.  
  29.  
  30.  
  31. Why use a relocatable heap?
  32. ---------------------------
  33.  
  34. RISC OS provides a non-relocatable heap manager. This means that the memory
  35. blocks are fixed in memory, and don't move about. The problem with this is
  36. that it gets very wasteful on memory when you have finished using the block.
  37. Say you loaded three files into a text editor:
  38.  
  39.   /--------\ Highest memory address
  40.   | File 3 |
  41.   |        |
  42.   |--------|
  43.   | File 2 |
  44.   |        |
  45.   |        |
  46.   |--------|
  47.   | File 1 |
  48.   \--------/ Lowest memory address
  49.  
  50. This is fine, no problems so far. However, suppose the user decided the close
  51. the file "File 2":
  52.  
  53.   /--------\ Highest memory address
  54.   | File 3 |
  55.   |        |
  56.   |--------|
  57.   | unused |
  58.   |        |
  59.   |        |
  60.   |--------|
  61.   | File 1 |
  62.   \--------/ Lowest memory address
  63.  
  64. The block of memory in the middle is now unused, and is wasting space. A
  65. non-relocatable heap manager can't do anything about this. Another example is
  66. if the user adds something to File 2, making it longer. File 2 will no longer
  67. fit in its original block - if you extended it then it would overwrite
  68. File 3. Therefore the heap manager has to copy the whole file up in memory,
  69. as shown in the diagram:
  70.  
  71.   /--------\ Highest memory address
  72.   | File 2 |
  73.   |        |
  74.   |        |
  75.   |        |
  76.   |--------|
  77.   | File 3 |
  78.   |        |
  79.   |--------|
  80.   | unused |
  81.   |        |
  82.   |        |
  83.   |--------|
  84.   | File 1 |
  85.   \--------/ Lowest memory address
  86.  
  87. WimpExtension provides a relocatable heap manager, however. This means that
  88. the heap manager is allowed to move the blocks about, to try and reduce the
  89. amount of wasted memory. In the situation above, for example, WimpExtension
  90. would move File 2 and File 3 down in memory, like so:
  91.  
  92.   /--------\ Highest memory address
  93.   | File 2 |
  94.   |        |
  95.   |        |
  96.   |        |
  97.   |--------|
  98.   | File 3 |
  99.   |        |
  100.   |--------|
  101.   | File 1 |
  102.   \--------/ Lowest memory address
  103.  
  104. As you can see, this can save a lot of memory.
  105.  
  106.  
  107.  
  108. Anchors
  109. -------
  110.  
  111. The only disadvantage of a reloctable heap is due to the fact that it IS
  112. relocatable - the blocks of memory aren't fixed and may move about. A
  113. question which immediately arises is "How do I find my memory block?" - if
  114. the block may have moved, how do you find it?
  115.  
  116. The answer is by using an "anchor". An anchor is a word in memory. The
  117. contents of this word is always a pointer to the start of the block. ie:
  118.  
  119.                       /-------\
  120.                       |       |
  121.   /--------\          |       |
  122.   | anchor |--------->| block |
  123.   \--------/          \-------/
  124.  
  125. The anchor always stays fixed in the same place in memory, so you always know
  126. where to find it. So, to find the location of your block, you would use:
  127.  
  128.   block%=!anchor% : REM block% now points to the first byte in the block
  129.  
  130. The anchors are stored all together at the beginning of the heap.
  131.  
  132.  
  133.  
  134. Size of blocks
  135. --------------
  136.  
  137. The word before the start of any block contains the size of the block in
  138. bytes. So to find the size of a block, you would use:
  139.  
  140.   size%=!(block%-4)
  141.  
  142. or:
  143.  
  144.   size%=!( (!anchor%) -4)
  145.  
  146. (because block%=!anchor%).
  147.  
  148. Due to the way the heap manager works, the size of a block is always four
  149. plus a multiple of eight (ie. 12, 20, 28, etc.). If you ask WimpExtension to
  150. make a block with a size which isn't four plus a multiple of eight, then the
  151. size will be rounded up by between one and seven bytes, to take it to the
  152. next largest acceptable size.
  153.  
  154.  
  155.  
  156. Initialising the heap
  157. ---------------------
  158.  
  159. Before you can use any of the heap operations, you must initialise the heap.
  160. This requires two parameters - the number of anchors to create initially, and
  161. the address in memory of the base of the heap.
  162.  
  163. The anchors are stored all together at the beginning of the heap. Because you
  164. need one anchor for every block in use, the number of anchors is effectively
  165. the maximum number of blocks you can have in use at any one time. You can
  166. create more anchors later, but it is best to create enough now, and then you
  167. don't have to worry about it later. Remember that anchors do take memory
  168. though, so don't go wild.
  169.  
  170. For example:
  171.  
  172.   SYS "WimpExt_Heap",0,base%,anchors%
  173.  
  174. Note that a heap which is empty (ie. no blocks are in use) takes absolutely
  175. no memory at all.
  176.  
  177.  
  178.  
  179. Allocating blocks
  180. -----------------
  181.  
  182. Whenever you ask WimpExtension to make you a new block (called "allocating" a
  183. block), it gives you a pointer to the anchor for that block. You must store
  184. the pointer to the anchor, NOT the pointer to the block, because the anchor
  185. will never move, but the block may do. For example, to ask WimpExtension for
  186. a block "size%" bytes long, you would use:
  187.  
  188.   SYS "WimpExt_Heap",2,,size% TO ,anchor%
  189.  
  190. If WimpExtension cannot create the block, because there is not enough free
  191. memory, then the anchor returned will be zero. You need to check for this
  192. before writing anything into the block. eg:
  193.  
  194.   SYS "WimpExt_Heap",2,,size% TO ,anchor%
  195.   IF anchor%=0 THEN ERROR 1,"Not enough free memory"
  196.  
  197.  
  198.  
  199. Freeing blocks
  200. --------------
  201.  
  202. When you have finished using a block, you use the "Free block" call to tell
  203. WimpExtension that you don't need the block any more, and the memory it takes
  204. up can be re-used. eg:
  205.  
  206.   SYS "WimpExt_Heap",3,anchor%
  207.  
  208. or:
  209.  
  210.   SYS "WimpExt_Heap",3,block%
  211.  
  212. The block will be added to WimpExtension's list of free blocks.
  213.  
  214.  
  215.  
  216. Reallocating blocks
  217. -------------------
  218.  
  219. Sometimes you will want to re-size a block - this is called "reallocating"
  220. the block. WimpExtension allows you to increase or decrease the size of any
  221. block at any time. eg:
  222.  
  223.   SYS "WimpExt_Heap",4,block%,new_size% TO ,flag%
  224.  
  225. or:
  226.  
  227.   SYS "WimpExt_Heap",4,anchor%,new_size% TO ,flag%
  228.  
  229. If the flag is zero on exit then the re-size failed because there wasn't
  230. enough free memory.
  231.  
  232. Note that this call may cause the specified block to move in memory. Only the
  233. specific block that you are re-sizing can move, though - all the other blocks
  234. will stay where they are.
  235.  
  236.  
  237.  
  238. Garbarge collection
  239. -------------------
  240.  
  241. "Garbage collection" is the whole point of the relocatable heap. This is the
  242. process of shuffling the blocks about in memory, so that no memory is wasted.
  243. For example, if the heap was in the following state:
  244.  
  245.   /---------\ Highest memory address
  246.   | block 2 |
  247.   |         |
  248.   |---------|
  249.   |  free   |
  250.   |         |
  251.   |         |
  252.   |---------|
  253.   | block 1 |
  254.   \---------/ Lowest memory address
  255.  
  256. then performing garbage collection would shuffle the blocks as follows:
  257.  
  258.   /---------\ Highest memory address
  259.   | block 2 |
  260.   |         |
  261.   |---------|
  262.   | block 1 |
  263.   \---------/ Lowest memory address
  264.  
  265. This then allows WimpExtension to decrease your task's WimpSlot, thus making
  266. this memory available to any other programs which might need it.
  267.  
  268. Two garbage collection calls are provided; the Tidy call:
  269.  
  270.   SYS "WimpExt_Heap",5
  271.  
  272. and the Compact call:
  273.  
  274.   SYS "WimpExt_Heap",6
  275.  
  276. The Tidy call just tidies the heap a little bit - the heap won't necessarily
  277. immediately be shuffled into the ideal position, but the call is usually
  278. quite fast. This call is intended to be called just before you call
  279. Wimp_Poll. If you set bit 3 of R2 when you called WimpExt_Initialise, then
  280. the heap will be automatically Tidied once a second, in WimpExt_PrePoll. Most
  281. of the time, you can just set this bit, and then forget all about garbage
  282. collection - it will all be handled for you.
  283.  
  284. The Compact call tidies the heap completely - the heap will immediately be
  285. shuffled into the ideal position. This call is often slower than the Tidy
  286. call, however, as it does more work.
  287.  
  288.  
  289.  
  290. How often should I tidy the heap?
  291. ---------------------------------
  292.  
  293. How often you tidy the heap depends on the average size of the blocks your
  294. program uses. If your program uses lots of little blocks then you should tidy
  295. the heap quite often. If it uses a smaller number of larger blocks then you
  296. should tidy it less often.
  297.  
  298. For a text editor, for example, the once-a-second tidy provided automatically
  299. should be fine. For something which uses smaller blocks, you should probably
  300. tidy the heap more often.
  301.  
  302.  
  303.  
  304. Finding the anchor of a block
  305. -----------------------------
  306.  
  307. If you have a pointer to a block, and you want to locate the block's anchor,
  308. then a call is provided to do this:
  309.  
  310.   SYS "WimpExt_Heap",7,block% TO ,anchor%
  311.  
  312. An error is produced if block% is not a valid pointer to the start of a
  313. block.
  314.  
  315.  
  316.  
  317. Fixing blocks
  318. -------------
  319.  
  320. Sometimes you may want to temporarily 'fix' the heap. This makes it so that
  321. all the blocks are fixed and cannot move. This is useful if you need to rely
  322. on a block staying put at the same position in memory for a while.
  323.  
  324. To fix the heap, you would use:
  325.  
  326.   SYS "WimpExt_Heap",8
  327.  
  328. and to unfix it you would use:
  329.  
  330.   SYS "WimpExt_Heap",10
  331.  
  332. Note that WimpExtension keeps a count of the number of times you haved fixed
  333. the heap, and only unfixes the heap when you tell it to the same number of
  334. times. ie:
  335.  
  336.   SYS "WimpExt_Heap",8
  337.   SYS "WimpExt_Heap",8
  338.   SYS "WimpExt_Heap",10
  339.  
  340. would leave the heap fixed. The following, however, would leave the heap
  341. unfixed, as the number of "unfixings" matches the number of "fixings":
  342.  
  343.   SYS "WimpExt_Heap",8
  344.   SYS "WimpExt_Heap",8
  345.   SYS "WimpExt_Heap",10
  346.   SYS "WimpExt_Heap",10
  347.  
  348. You can force WimpExtension to unfix the heap straight away, regardless of
  349. the number of times it has been fixed, using the following call:
  350.  
  351.   SYS "WimpExt_Heap",9
  352.  
  353. ie. The following would leave the heap unfixed:
  354.  
  355.   SYS "WimpExt_Heap",8
  356.   SYS "WimpExt_Heap",8
  357.   SYS "WimpExt_Heap",9
  358.  
  359.  
  360.  
  361. Creating more anchors
  362. ---------------------
  363.  
  364. WimpExtension allows you to create more anchors, even while the heap is in
  365. use. Note that this call has to move the entire heap up in memory, so it can
  366. be quite slow. For example:
  367.  
  368.   SYS "WimpExt_Heap",11,add%
  369.  
  370. "add%" extra anchors will be created. All the blocks will be moved.
  371.  
  372. WimpExtension also provides a call to allocate a block, automatically
  373. creating more anchors if you've run out:
  374.  
  375.   SYS "WimpExt_Heap",12,,size% TO ,anchor%
  376.  
  377.  
  378. Freeing all blocks
  379. ------------------
  380.  
  381. WimpExtension provides a call to free all the blocks in the heap:
  382.  
  383.   SYS "WimpExt_Heap",13
  384.  
  385. Every single allocated block will be freed, and all the memory released.
  386.  
  387.  
  388.  
  389. Describing the heap
  390. -------------------
  391.  
  392. WimpExtension provides a call which provides various bits of information
  393. about the heap:
  394.  
  395.   SYS "WimpExt_Heap",1 TO ,,largest%,free%,heapsize%,anchors%,blocks%
  396.  
  397.   largest%  : The size of the largest continuous area of memory in the heap
  398.   free%     : The total amount of memory free in the heap
  399.   heapsize% : The total amount of memory used by the heap
  400.   anchors%  : The number of anchors which have been created
  401.   blocks%   : The number of blocks which are currently allocated
  402.